|
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph ''K''6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph. Any of the graphs in the Petersen family can be transformed into any other graph in the family by Δ-Y or Y-Δ transforms, operations in which a triangle is replaced by a degree-three vertex or vice versa. These seven graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked.〔 They are also among the forbidden minors for the YΔY-reducible graphs.〔〔 ==Definition== The form of Δ-Y and Y-Δ transforms used to define the Petersen family is as follows: *If a graph ''G'' contains a vertex ''v'' with exactly three neighbors, then the Y-Δ transform of ''G'' at ''v'' is the graph formed by removing ''v'' from ''G'' and adding edges between each pair of its three neighbors. *If a graph ''H'' contains a triangle ''uvw'', then the Δ-Y transform of ''H'' at ''uvw'' is the graph formed by removing edges ''uv'', ''vw'', and ''uw'' from ''H'' and adding a new vertex connected to all three of ''u'', ''v'', and ''w''. These transformations are so called because of the Δ shape of a triangle in a graph and the Y shape of a degree-three vertex. Although these operations can in principle lead to multigraphs, that does not happen within the Petersen family. Because these operations preserve the number of edges in a graph, there are only finitely many graphs or multigraphs that can be formed from a single starting graph ''G'' by combinations of Δ-Y and Y-Δ transforms. The Petersen family then consists of every graph that can be reached from the Petersen graph by a combination of Δ-Y and Y-Δ transforms. There are seven graphs in the family, including the complete graph ''K''6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph ''K''4,4, and the seven-vertex complete tripartite graph ''K''3,3,1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Petersen family」の詳細全文を読む スポンサード リンク
|